//
//  XBTree.c
//  数据结构算法和笔试题
//
//  Created by 王国栋 on 16/6/20.
//  Copyright © 2016年 xiaobai. All rights reserved.
//

#include "XBTree.h"
#include "XBLinkList.h"
// tree是n个节点的有限集合，n = 0是称为空树，在任意一个非空树种，有且仅有一个特定的根节点，n>1时，其余节点可分为m(m>0)个互不相交的有限集合
//T1,T2...TM 每个集合本身是一棵树，称为根节点的子树。

// 节点分类：根节点，叶子节点（终端节点),节点拥有的子树的个数称为度
// 森林是m个互不相交的树的集合。



// 树的存储结构

//----1.双亲表示法：每个节点都表明双亲节点的

//一个节点
typedef struct XBParentTreeNode
{
    int parentIdx;
    DATATYPE data;//数据
    
}XBParentTreeNode;

typedef struct XBParentTree
{
    XBParentTreeNode tree[MAX_SIZE];
    int rootIdx,nodeNum;
}XBParentTree;
/*:
 *   这样的存储结构，查找一个节点的双亲节点时间复杂度为O(1),但是查找子节点却需要遍历整个数组。所以可以增加一个字段firstchild，表示最左边的子树，
 
     为了增加兄弟树之间的关系可以再增加一个字段rightB,表示当前树的右边的树。 上面的关系在一个树最多有两个子树的时候是非常合理的。
 
     如果节点的孩子比较多，可以把结构扩展为有双亲，长子，右兄弟字段。结构是根据不同的需求设计的
 

 */


// --- 2.孩子表示法


//2.1 这里子树的个数是用链表保存的，可以克服采用固定数组带来的空间浪费问题，但是时间上会带来损耗
typedef struct XBChildTreeNode
{
    DATATYPE data;
    int degree;//树的度，表示子树的个数
    XBLinkNode * child;//链表，每个元素存储的数据类型表示本节点的子树的节点所在的索引。
    
}XBChildTreeNode;

typedef struct XBChildTree
{
    XBChildTreeNode tree[MAX_SIZE];
    int rootIdx,nodeNum;
}XBChildTree;

// ---- 下面是优化的结构

// 把每个节点的孩子节点排列起来，以单链表作为存储结构，n个节点n个孩子链表，如果是叶子节点，单链表为空。然后再把n个头指针放在一个数组里面
typedef struct XBChild
{
    int idx ;//当前的索引
    struct XBChild * next;//链表,子树的索引按顺序排列
    
}XBChild,*XBChildPtr;
typedef struct XBChildNode2
{
    DATATYPE  data;//当前的索引
    XBChildPtr firstchild;
    int parentIdx;//双亲节点的索引
}XBChildNode2;

typedef struct XBChildTree2
{
    XBChildNode2 tree[MAX_SIZE];
    int rootN,nodeNum;
    
}XBChildTree2;

// ---- 孩子兄弟表示法，变成了一个『二叉树』

typedef struct XBBroNode{
    
    DATATYPE data;
    struct XBBroNode * parentNode;//父节点的
    struct XBBroNode * firstChild,*rightBrother; //分别表示第一个孩子的节点和右边的兄弟节点组成的链表。不是仅仅节点
}XBBroNode;


















